package com.paic.du.lib.sort;

import com.paic.du.lib.Utils;;
public class MergeSort {
	public static void merge(int []ori,
			int _left1, int _right1, int _left2, int _right2){
		int l1,r1,l2,r2;
		l1=_left1;
		l2=_left2;
		r1=_right1;
		r2=_right2;
		int index=0;
		int k[] = new int [_right2-_left2+_right1-_left1+2];
		while(l1<=r1&&l2<=r2){
			if(ori[l1]<ori[l2])
				k[index++]=ori[l1++];
			else
				k[index++]=ori[l2++];
		}
		while(l1<=r1)
			k[index++]=ori[l1++];
		while(l2<=r2)
			k[index++]=ori[l2++];
		index=0;
		int left=Utils.min(_left1,_left2);
		
		while(index<k.length)
			ori[left+index]=k[index++];
		
			
	}

	public static void mergeSort(int m[],
			int _left, int _right){
		
		int length=_right-_left;
		int split=(length)/2+_left;
		if(_left>=_right) return;
		mergeSort(m, _left, split);
		mergeSort(m, split+1, _right);
		merge(m, _left, split, split+1, _right);
		
	}
	
	public static void main(String args[]){
		int m[] = Utils.ori;
		mergeSort(m, 0, m.length-1);
		for (int i=0;i<m.length;i++)
		System.out.println(m[i]);
	}
}
